import java.util.Comparator;
import java.util.PriorityQueue;

public class Test1 {

    static class Node {
        int weight;
        Node left;
        Node right;

        public Node(int x) {
            this.weight = x;
            this.left = null;
            this.right = null;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "weight=" + weight +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

    private static Node createNode(int x) {
        return new Node(x);
    }

    //构建哈夫曼树
    public static Node huffumanTree(int[] a) {
        //1.创建一个优先级队列
        PriorityQueue<Node> nodes = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.weight - o2.weight;
            }
        });
        //2.将权值结点入队
        for (int i = 0; i < a.length; i++) {
            Node node = createNode(a[i]);
            nodes.offer(node);
        }
        //3.开始构建
        while (!nodes.isEmpty()) {

            //取第一个值
            Node node_1 = nodes.poll();
            if (nodes.isEmpty()) {
                return node_1;
            }
            //取第二个值
            Node node_2 = nodes.poll();
            //保证左子树的权值小于右子树
            if (node_1.weight > node_2.weight) {
                Node tmp = node_1;
                node_1 = node_2;
                node_2 = tmp;
            }
            Node top = createNode(node_1.weight + node_2.weight);
            top.left = node_1;
            top.right = node_2;
            nodes.offer(top);
        }

        return nodes.peek();
    }

    //打印哈夫曼树：前序遍历
    public static void printfCode(Node root, String str) {
        if (root.left == null) {
            System.out.println("结点为：" + root.toString() + ";" + "对应的哈夫曼编码是：" + str);
            return;
        }

        printfCode(root.left, str + "0");
        printfCode(root.right, str + "1");
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 43, 90, 7};
        Node node = huffumanTree(a);
        printfCode(node, "");

    }
}